import java.util.Stack;

/**
 * @Author zhang lei
 * @Date 2021-11-14 16:28
 */
public class Algo122股票买卖 {
    public static int maxProfit(int[] prices) {
        int profit = 0;
        Stack<Integer> s = new Stack<Integer>();
        for(int i = prices.length-1; i>=0;i--) {
            int cur = prices[i];
            int low = -1;
            int max = -1;
            while(!s.isEmpty() && cur>s.peek()) {
                while (!s.isEmpty()) {
                    int one = s.pop();
                    if(low == -1) {
                        low = one;
                    }else {
                        max = one;
                    }
                }
            }
            if(low != -1 && max != -1) {
                profit += max - low;
            }
            s.push(cur);
        }
        return profit;
    }

    public static void main(String[] args) {
        int[] prices = {1,2,3,4,5};
        System.out.println(maxProfit(prices));
    }
}
